1. Field of the Invention
This invention relates to compilation of computer programs, and more particularly, to dynamic loop transfer in dynamic compilation environments.
2. Description of Background
The instructions that a processor within a computer system executes are ultimately determined by a programmer, but typically, the programmer will write higher-level-language “source code” that computer programs use to generate machine-level instructions that are actually evaluated during execution. A compiler is a computer program module that translates source code into object code, which is written in a lower-level computer language that has a form suitable for processing by a target platform. Different hardware platforms are configured to process different native code forms and therefore require different compilers. A typical compiler may perform operations such as lexical analysis, preprocessing, parsing, semantic analysis, code generation, and code optimization. Code optimization is the process of tuning the object code output to minimize some attribute (or maximize the efficiency) of the executable program.
Static compilers perform compilation by converting source code to machine code that can be directly executed on the target platform. To gain performance during program execution, some programming language implementations can utilize dynamic compilers instead. Dynamic compilation entails the generation of code at runtime; that is, program code is dynamically constructed during execution of the program while other code in the same system is being evaluated. This can allow for optimizations to be made that can only be known at runtime.
Advanced implementations of modern object-oriented languages, such as Java, depend on runtime environments that employ “just-in-time” (JIT) compilation for performance. These language environments dynamically compile program code that is loaded incrementally, possibly from a remote target. While programs are running, JIT compilers selectively compile the most frequently executing methods to native code, which is code that is intended to directly run on the same type of computer and operating system upon which the compiler itself is running. JIT compilers compile separate code sequences one at a time, as they execute or “on the fly”, into equivalent sequences of the native code of the underlying machine, to improve the runtime performance. A JIT compiler may only compiles a code path when it knows the code path is about to be executed. This approach allows the program to start up more quickly, as a lengthy compilation phase is not needed before any execution can begin.
Because overall program execution time will include compilation overhead when using a JIT compiler, it is important for the JIT compiler to be fast and lightweight, as well as to generate high-quality native code. One particular concern is that, while dynamic and on-the-fly compilation techniques such as JIT compilation have the potential to significantly improve program performance, optimization implementation can be challenging because some optimizations that could be done at the initial compile time are delayed until further compilation at runtime. This can force the compiler to predict which optimizations will be most successful for the remainder of program execution.
One approach to enable more aggressive optimizations for JIT-based virtual machines is to specialize the program for a particular behavior or set of execution conditions and then to undo the optimization when conditions change. This enables the compiler to identify optimizations that are likely to be successful in the near-term, and then apply others as it learns more about future program and resource behavior. Examples of such optimizations include virtual call inlining, exception handler removal, and memory management system optimizations.
The presence of an efficient, general-purpose mechanism for undoing optimization on-the-fly when associated assumptions are rendered invalid is important to ensure that future method invocations can be handled by recompilation. The process performed by such a mechanism, which allows execution control to change midway through from the mode of evaluating the currently executing method to the mode of compiling a replacement version of the method and then reinitiating execution of the new version in native code, is termed dynamic loop transfer or on-stack replacement. Dynamic loop transfer can be used to enable enhancements such as debugging optimized code via de-optimization, deferred compilation to improve compiler speed and/or code quality, online optimization of activations containing long-running loops, and optimization and code generation based on speculative program invariants.
One example of a dynamic loop transfer implementation is that provided by Sovereign, a JIT compiler developed by IBM for the AIX operating system platform. Sovereign performs dynamic loop transfer by carefully arranging the compiled code of the targeted method into a multiple-entry method body. This is done so that the previously compiled method can be used for new calls to the method while still separately allowing the method's particular execution state at the time of extraction to be mapped into a stack activation frame to allow the recompiled counterpart to be used for continuing execution where interpretation left off.
A drawback to the Sovereign approach is that it is error prone. Arrangement of the compiled code into the method body must be carefully performed for each targeted method because the execution state at the dynamic entry point in the recompiled method needs to match the execution state at the time of extraction. There are many JIT optimization processes need to be able to properly take into account the expected replacement entry point to avoid making changes to the method body that would prevent the transfer to the correct entry point in the recompiled method. This requires that the execution state be mapped into a new activation frame that is arranged to match the expected transfer entry point of the recompiled method. The occurrence of multiple entry points can lead some optimizations to loop endlessly because dataflow algorithms fail to converge. Furthermore, the Sovereign approach operates to disable many code optimizations and therefore can degrade performance by generating code that is less optimal then normal.